/**
 * 剑指 Offer 55 - II. 平衡二叉树
 * https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof/
 */
const { createTreeNode } = require('../../libs/public');

/**
 * @param {TreeNode} root
 * @return {number}
 */
function dfs(root) {
  const leftDepth = root.left ? dfs(root.left) : 0;
  if (leftDepth < 0) {
    return leftDepth;
  }
  const rightDepth = root.right ? dfs(root.right) : 0;
  if (rightDepth < 0) {
    return rightDepth;
  }
  if (Math.abs(leftDepth - rightDepth) > 1) {
    return -1;
  }
  return Math.max(leftDepth, rightDepth) + 1;
}

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
function isBalanced(root) {
  if (!root) {
    return true;
  }
  return dfs(root) >= 0;
}

console.log(isBalanced(createTreeNode([3, 9, 20, null, null, 15, 7])) === true);
console.log(isBalanced(createTreeNode([1, 2, 2, 3, 3, null, null, 4, 4])) === false);
